package J20250121_Dynamic;
import java.util.*;
/**
 * Created with IntelliJ IDEA.
 * Description: 动态规划55——58
 * User: 王圆豪
 * Date: 2025-02-18
 * Time: 22:49
 */
public class Solution9 {
    //零钱兑换II——https://leetcode.cn/problems/coin-change-ii/description/
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n+1][amount+1];
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                dp[i][j] = dp[i-1][j];
                if(j >= coins[i-1]) dp[i][j] += dp[i][j-coins[i-1]];
            }
        }
        return dp[n][amount];
    }

    //完全平⽅数——https://leetcode.cn/problems/perfect-squares/
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        int INF = 0x3f3f3f3f;
        for(int i = 1; i <= n; i++) dp[i] = INF;
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= n; j++){
                if(j >= i*i && dp[j-i*i] != INF){
                    dp[j] = Math.min(dp[j], dp[j-i*i] +1);
                }
            }
        }
        return dp[n] <= INF ? dp[n] : 0;
    }

    //⼀和零——https://leetcode.cn/problems/ones-and-zeroes/
    public int findMaxForm(String[] strs, int m, int n) {
        int z = strs.length;
        int[][][] dp = new int[z+1][m+1][n+1];
        HashMap<String, int[]> map = new HashMap<>();
        for(int i = 0; i < z; i++){
            int a = 0, b = 0;
            for(int j = 0; j < strs[i].length(); j++){
                if(strs[i].charAt(j) == '0') a++;
                else b++;
            }
            map.put(strs[i], new int[]{a,b});
        }
        for(int i = 1; i <= z; i++){
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    int[] arr = map.get(strs[i-1]);
                    int a = arr[0], b = arr[1];
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= a && k >= b){
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i-1][j-a][k-b] + 1);
                    }
                }
            }
        }
        return dp[z][m][n];
    }

    //盈利计划——https://leetcode.cn/problems/profitable-schemes/
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int m = group.length;

        int[][][] dp = new int[m+1][n+1][minProfit+1];
        for(int i = 0; i <= n; i++) dp[0][i][0] = 1;
        for(int i = 1; i <= m; i++){
            for(int j = 0; j <= n; j++){
                for(int k = 0; k <= minProfit; k++){
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= group[i-1]){
                        dp[i][j][k] += dp[i-1][j-group[i-1]][Math.max(0, k-profit[i-1])];
                    }
                    dp[i][j][k] %= ((int)Math.pow(10,9) + 7);
                }
            }
        }
        return dp[m][n][minProfit];
    }
}
